// https://www.lintcode.com/problem/palindrome-partitioning/description

class Solution {
public:
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    bool isPalin (string s)
    {
        for (int l = 0, r = s.length() - 1; l < r; l++, r--)
        {
            if (s[l] != s[r]) return false;
        }
        return true;
    }
    void help(string s, vector<vector<string>>& result, vector<string>& tmp)
    {
        if (s.length() == 0) 
        {
            result.push_back(tmp);
            return;
        }
        for (int i = 0; i < s.size(); ++i)
        {
            string t = s.substr(0, i + 1);
            if (isPalin(t)) 
            {
                tmp.push_back(t);
                help(s.substr(i + 1), result, tmp);
                tmp.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string &s) {
        vector<vector<string>> result;
        vector<string> tmp;
        help(s, result, tmp);
        return result;
    }
};